import javax.swing.text.html.HTMLEditorKit;
import java.util.Stack;

public class BinaryTreeTraversalRecursion {
    static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.value = val;
        }
    }

    private TreeNode head;

    public void createTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        head = node1;
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right =node7;
    }

    //先序遍历非递归
    public void preOder(){
        if(head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(head);
            while(!stack.isEmpty()) {
                TreeNode peek = stack.pop();
                System.out.print(peek.value + " ");
                if(peek.right != null) {
                    stack.push(peek.right);
                }
                if(peek.left != null) {
                    stack.push(peek.left);
                }
            }
            System.out.println();
        }
    }

    //中序遍历非递归
    public void inOder() {
        if(head != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = head;
            while(!stack.isEmpty() || cur != null) {
                if(cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }else {
                    TreeNode peek = stack.pop();
                    System.out.print(peek.value + " ");
                    cur = peek.right;
                }
            }
            System.out.println();
        }
    }

    //后序遍历非递归(两个栈实现)
    public void posOrder1() {
        if(head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.add(head);
            while(!stack.isEmpty()) {
                TreeNode peek = stack.pop();
                collect.push(peek);
                //System.out.print(peek.value + " ");
                if(peek.left != null) {
                    stack.push(peek.left);
                }
                if(peek.right != null) {
                    stack.push(peek.right);
                }
            }
            while (!collect.isEmpty()) {
                System.out.print(collect.pop().value + " ");
            }
            System.out.println();
        }
    }


    //后序遍历非递归(一个栈实现)
    public void posOrder2() {
        if(head != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode h = head;
            stack.push(h);
            while(!stack.isEmpty()) {
                TreeNode cur = stack.peek();  //获取栈顶元素
                if(cur.left != null && cur.left != h && cur.right != h) {  //左树不为空 并且 左树和右树都没处理过
                    stack.push(cur.left);
                }
                else if(cur.right != null && cur.right !=h) { //右树不为空，并且右子树还没处理过
                    stack.push(cur.right);
                }
                else {  //左子树和右子树都为空 或者 都已经处理过了
                    System.out.print(cur.value + " ");
                    h = stack.pop();  //标记上一个处理过的树
                }
            }
            System.out.println();
        }
    }


}
